The present invention relates to an interleaving and de-interleaving method of a communication system, and more specifically, to a block interleaving and de-interleaving method and address generator thereof.
The main function of channel coding is to detect and correct errors induced by random noise occurring in transmission in the wireless communication system. Transmission errors happen randomly and are thus usually distributed evenly in the data. Burst error, however sometimes occurs during transmission, and is likely to exceed the error detection or error correction abilities of the encoder/decoder, requiring retransmission if the errors cannot be corrected. Interleaving is a method of improving burst error correction ability. The interleaving process re-orders data (i.e. the coded symbols) before transmission. When a burst error occurs during transmission, errors are dispersed by performing the corresponding de-interleaving process. The encoder is able to improve the error correction ability by reducing the likelihood of long consecutive errors. The address generator for interleaving, or the interleaver, is an apparatus that changes the order of the coded symbols in the transmitter, whereas the address generator for de-interleaving, or the de-interleaver, is a corresponding apparatus assembling the coded symbols into their original order.
Block interleaving is one of the most common and easily performed interleaving methods. The block interleaving method permutes the coded symbols in blocks from the encoder, and rearranges the coded symbols. Permutation is normally performed by filling a matrix with coded sequences by row, then outputting to the modulator by column. As shown in FIGS. 1A and 1B, block interleaving is explained using a matrix with C columns and R rows. FIG. 1A shows the filling order of the matrix at the transmitter, wherein the coded symbols {0, 1, 2, 3, 4, 5, . . . , M-3,M-2,M-1} are filled into the matrix by row. The total number of coded symbols (M) is 26, and the column value (C) is 4 in this example. The row value (R) is thus 6, the whole number obtained from dividing 26 by 4, and the remainder (W) is 2. As shown in FIG. 1A, there are R complete rows and an incomplete row, which is the (R+1)st row with only W coded symbols. As shown in FIG. 1B, the sequence of columns is then permuted before input to the modulator. In this example, the block interleaver swaps the second and the third columns. The interleaving operation is accomplished by outputting the coded symbols {0, 4, 8, . . . , 2, 6, 10, . . . 1, 5, 9, . . . 3, 7, 11, . . . } from the matrix by column. At the receiver, the de-interleaver performs the inverse operation.
In a typical case, both the interleaver and de-interleaver read the coded symbols from the memory cells, and then write the coded symbols after performing interleaving or de-interleaving into other memory cells. This kind of interleaving or de-interleaving operation requires accessing the memory twice for each coded symbol. Since the M coded symbols must be filled before they can be read out, twice as many memory cells as coded symbols (2M) are required. Furthermore, since the interleaver writes the coded symbols by row and reads the coded symbols by column, a complete column can only be obtained for input to the modulator when the first coded symbol of the last row is filled in the matrix. In other words, C(R−1)+1 memory cells must be filled before the interleaver begins input of the coded symbols to the modulator. A minimum delay time is therefore the time required to access the memory C(R−1)+1 times.